//给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 
//
// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0]
//输出：[[],[0]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10 
// -10 <= nums[i] <= 10 
// nums 中的所有元素 互不相同 
// 
// Related Topics 位运算 数组 回溯 👍 1391 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class _78_Subsets {
    public static void main(String[] args) {
        int[] nums = new int[] {1,2,3};
        Solution solution = new _78_Subsets().new Solution();
        List<List<Integer>> res = solution.subsets(nums);
        System.out.println(res);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            int n = nums.length;

            for (int i = (int) Math.pow(2, n); i < (int) Math.pow(2, n + 1); i++) {
                // 这个语句很妙
                String bitmask = Integer.toBinaryString(i).substring(1);

                List<Integer> cur = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    if (bitmask.charAt(j) == '1') {
                        cur.add(nums[j]);
                    }
                }
                res.add(cur);
            }
            return res;
        }

        /**
         * 答案方法：递归
         * @param nums
         * @return
         */
        public List<List<Integer>> subsets_digui(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            res.add(new ArrayList<>());

            for (int num : nums) {
                List<List<Integer>> newSubsets = new ArrayList<>();
                for (List<Integer> subset : res) {
                    List<Integer> newSubset = new ArrayList<Integer>(subset);
                    newSubset.add(num);
                    newSubsets.add(newSubset);
                }
                res.addAll(newSubsets);
            }
            return res;
        }
        /**
         * 自己写的回溯算法
         * @param nums
         * @return
         */
        public List<List<Integer>> subsets_backtrack(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i <= nums.length; i++) {
                backtrack(nums, res, tmp, 0, i);
            }
            return res;
        }

        private void backtrack(int[] nums, List<List<Integer>> res, List<Integer> tmp, int index, int need) {
            if (0 == need) {
                res.add(new ArrayList<>(tmp));
                return;
            }

            for (int i = index; i < nums.length; i++) {
                tmp.add(nums[i]);
                backtrack(nums, res, tmp, i + 1, need - 1);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}